1. Field of Invention
This invention pertains to mobile computers. It enables a group of such computers to share information and query information stored in the group (the global database).
2. Prior Art
A Mobile Ad-hoc NETwork (MANET) is a set of mobile peers (sensors, PDA'S, Blackberry's, vehicles, etc.) that communicate with each other via short range wireless protocols, such as IEEE 802.11, Bluetooth, Zigbee, or Ultra Wide Band (UWB) (see FIG. 1). Consider a database that is distributed among the peers of the MANET. On each mobile peer there is a local database that stores and manages a collection of reports. A report is a set of values sensed by the peer, entered by the user, or otherwise obtained by a mobile peer. Often a report describes a physical resource such as an available parking slot.
All the local databases maintained by the mobile peers form the MANET database. The peers communicate reports and queries to neighbors directly, and the reports propagate by transitive multi-hop transmissions. FIG. 2 illustrates a MANET database.
Generally, there are two paradigms to conduct MANET data dissemination, namely state-full and stateless. In state-full dissemination, a routing structure is imposed and maintained among the mobile peers (e.g., [1]). State-full dissemination may be ineffective in a large and highly mobile MANET, since the routing structure quickly becomes obsolete. It is also ineffective in sparse and loosely connected networks in which a routing structure cannot cover the whole network. In stateless dissemination, the intermediate peers save reports and later (as new neighbors are discovered) transfer these reports. In the literature this paradigm is also called stateless gossiping, epidemic, or store-and-forward dissemination. This invention addresses the stateless paradigm for reports dissemination. Our invention does not rely on any infrastructure, central server, or routing data structures. Any subset of peers will be able to separate from the network and share information by stateless dissemination.
The problem with the store-and-forward dissemination is that the reports that need to be stored and forwarded by a node may exceed its storage, bandwidth, and energy capacities. Here is where two innovative aspects of the present patent come into play.
1. Adaptive control of transmission size or inter-transmission period. This invention includes a strategy by which a mobile node dynamically adjusts the number of reports included in a transmission or the period of time between two consecutive transmissions to other mobile peers. The number depends on the period of time between two consecutive transmissions (the longer the period, the larger the number of reports that the peer is allowed to communicate), the available energy, the bandwidth, and the contact time between encountering neighbors. The inter-transmission period depends on the number of reports included in a transmission, the available energy, the bandwidth, and the contact time between encountering neighbors. With such adaptive control of transmission size, the number of collisions is minimized and the available bandwidth is optimally utilized.
2. Reports prioritization. Given the bandwidth, energy, and memory constraints for the mobile peers, we believe that ranking of alerts is important in MANET databases, so that the most important reports are transmitted and saved. Therefore this invention includes a ranked store-and-forward method (called MARKET) for reports dissemination. The rank of a report may depend on factors such as its demand (how important it is to the mobile nodes), its supply (how many mobile nodes have already received it), and its size.
2.1 Patents
Data/Information Dissemination in Mobile Wireless Environments
Patents [16-21] require dedicated apparatuses such as data servers or base stations to collect and disseminate data. Our system does not require any such apparatuses. In patents [26, 27], data is disseminated among vehicles in a peer-to-peer fashion without relying on any dedicated infrastructure. However, these patents do not address bandwidth/power management (how much to transmit, what to transmit) and memory management (what to save), whereas we do. These issues are important because in many mobile P2P environments at least one limitation (bandwidth, power, or memory) is a concern.
Resource/Service Discovery in Mobile Wireless Environments
Patents [22, 24] require directory agents be selected from the mobile peers. The directory agents collect resource information and deliver it to other mobile peers upon requests. This paradigm is not suitable for a high mobility environment as it is difficult to conduct a selection of directory agents in such an environment. In addition, there may not be a path from a mobile peer to any directory agent. Patent [23] addresses the issue of choosing from multiple network interfaces a right one to deliver a resource request. In [25], each mobile peer periodically transmits a set of resources by multicasting. The advertised resources may be produced by the peer itself or by other peers, i.e., there is brokering. However, [25] does not provide solutions to questions such as how many resources are included in each transmission, how to select the resources to transmit, and so on, whereas our system addresses these issues.
Mobile Ad-hoc Networks
Many patents (see [34-44]) concern routing a message to a specific destination given by the network address or the location. In our case the network addresses or the locations of the destinations (i.e. consumers) are not known a priori. Other patents ([28-33]) disclose systems and methods for seamless and cost efficient access to the infrastructure network. For example, in [30, 31], mobile ad hoc networks are used as a bridge to the cellular network. For another example, [32] discloses a method in which a mobile device that is accessing the internet via a cellular infrastructure automatically switches to the home wireless network when getting home. Our system concentrates on data management within the mobile ad hoc network rather than establishing a communication path from a mobile device to the infrastructure network. Patents [45, 46] deal with power management in ad hoc networks. They do so by adjusting the transmission power such that the source-to-destination throughput is optimized or a certain connectivity constraint is satisfied. We deal with power efficiency by brokering the reports that are mostly likely to be useful to other peers.
2.2 Scientific Papers
Prioritization in mobile peer-to-peer data dissemination. Ranking reports for memory (cache) management and bandwidth management in mobile peer-to-peer networks has been studied in a number of works. In [3] reports are ranked randomly. In [9] the rank of a report for storage only is jointly determined by its demand, reliability, and size, but not on supply. Our comparison with RANDI demonstrates the importance of supply. In [11] reports are ranked based on their spatio-temporal relevance. The relevance indicates, for example, the probability that a parking slot reported by the report will be still available when the user reaches it. This relevance can be incorporated into MARKET by having the rank of a report weighted by its relevance (see footnote 4). In [13][6] reports are ranked based on an abstract utility function which is to be defined by specific applications. Our ranking method can be viewed as an instantiation of the utility function.
Delay/Fault-Tolerant Mobile Sensor Networks [14]. This work studies how to efficiently deliver reports from sensors to sinks in disconnected mobile sensor networks. It is assumed that every sink is interested in receiving every sensor-produced report. In our context, there are queries and they may be different for different sinks, and these have significant implications in the P2P interaction mode and reports ranking.
Resource discovery (e.g. [12]) and Publish/subscribe (e.g. [1]) in MANET's. These papers often build a routing structure for resource information dissemination. Consequently they can be inefficient, particularly in networks that are prone to frequent topology changes and disconnections due to mobility and turn-over. In such an environment, either a lot of communication has to be expended to keep the routing structure up to date, or the routing structure rapidly becomes obsolete and misses many matches. Furthermore, these methods depend on network connectivity, and do not work in sparse networks.
Cooperative caching in mobile environments. The MARKET algorithm performs a form of cooperative caching; the local database of each mobile peer is a cache that services a query originator in the QR operation. However, in most of the existing work on cooperative caching (see e.g., [2][8]), a report is cached at a mobile peer when it is queried by the mobile peer itself or by some other peer. In other words, the caching is reactive. This does not provide good data access in a sparse environment, because the query does not propagate out, and thus there is no cache. The MARKET algorithm, on the other hand, proactively transmits reports during an encounter, so as to enhance the receiver's capability as a broker. This enables data access in a sparse environment.
Energy-efficient broadcasting in MANET's. The work in this area (see [10] for a survey) studies how to flood a single message to all the nodes in a connected MANET with minimum energy consumption. MARKET differs from MANET broadcasting in several aspects. First, the objective of MARKET is to deliver each report to as many mobile peers that are interested in them as possible, rather than delivering the report to all the mobile peers. Second, MARKET does not require a contemporaneous path between the report producer and a report consumer, whereas MANET broadcasting does. Finally, MARKET deals with a continuous process of data dissemination rather than the flooding of a single message.
3. Objects and Advantages
This invention develops a MANET database without a central point of failure or reliance on servers. The database will be used to disseminate reports throughout the MANET. The heart of our invention is a distributed method that disseminates reports intelligently in an adaptive manner. Using this method, each mobile peer makes local decisions on when to disseminate reports, how many to disseminate, and which reports to disseminate. With the local decisions made by each individual peer, the whole MANET database maximizes the number and timeliness of reports disseminated to the mobile nodes, under the bandwidth, energy, and memory constraints.
The invention, called MOBIDIK (MOBIle DIscovery of local Knowledge), is a software technology embedded in mobile devices such as cell phones, PDA'S, laptops, etc. It will provide a user the ability to search for local resources such as a person of interest, a restaurant, or a parking slot. The search is conducted in a peer-to-peer rather than client/server (a la Google) mode.
When there is a community of mobile devices near each other and they communicate with each other, they form a network called a Mobile Peer-to-peer (MP2P) network. MOBI-DIK provides advanced communication control, information dissemination, power management, resource discovery, and filtering algorithms to greatly enhance the capabilities of MP2P networks, facilitating more robust applications and extending the range of communication.
MOBI-DIK allows a mobile device to satisfy a local search by communicating with encountered devices in a multi-hop, self-forming network, to propagate information, and to obtain new information in exchange. It is particularly useful for searching highly-relevant (in time, space, and interest) resources in a local environment, such as a person with certain qualifications at a convention, an available parking slot, a nearby taxicab or restaurant, or the rapid dissemination of an image of a person of interest to first responders.
3.1. Commercial Applications and their Rationale
MOBI-DIK can be used to enable mobile local search. Mobile local search is a procedure in which a mobile user searches for local resources, i.e. resources that are in geographic proximity to the mobile user (e.g., enemy engagements or other incidents in a convoy, a person with certain expertise in a convention hall, a ride-share opportunity, a taxi-cab, a parking slot, etc). In mobile local search applications the local resources that are of interest to mobile users are often only available during a limited period of time and these resources themselves may be mobile. For example, a cab driver wants to find a customer nearby. The customer may be moving and she is available only until she hires a cab. Similarly, the current traffic speed on a road segment, the available parking slots around a driver, the available workstations in a large convention hall, are temporarily valid or available resources. We call these spatio-temporal resources, in the sense that the resources or events are relevant in a limited geographic area, and for a limited time duration. Mobile local search for spatio-temporal resource is a special case of resource discovery and publish/subscribe applications.
Google or local.com currently provide static local information, but not dynamic of the type described above. A local server may not exist due to lack of a profitable business model, and if it exists it may be unavailable (such servers are unlikely to have the reliability of global sites such as Google), or the data may not be available for several reasons such as propagation delays (think of sudden-brake information that needs to be propagated to a server and from there to the trailing vehicles), or due to device limitations (e.g. a smart cell-phone may have Bluetooth but not internet access), etc. Furthermore, even if the infrastructure and a server are both available, a user may not be willing to pay the dollar-cost that is usually involved in accessing the server through the licensed spectrum, or, the server may accept only data from certain users, or only data related to certain applications but not others. An infrastructure may also not be available in military/combat situations, disaster recovery, in a commercial flight, etc. Thus, MOBI-DIK substitutes or augments the client-(local)-server approach by a MANET approach in which devices communicate with each other via short range wireless communication. MOBI-DIK has many potential commercial applications, including:
Social Networks. In a large professional, political, or social gathering, MOBI-DIK is useful to automatically facilitate a face-to-face meeting based on matching profiles. For example, in a professional gathering, MOBI-DIK enables attendees to specify queries (interest profiles) and resource descriptions (expertise) to facilitate conversations, when mutual interest is detected. This opportunistic matchmaking can greatly enhance the value of networking events allowing users to connect with targeted, interested parties without a priori knowledge of their name, title, phone number, or other personal information. A face-to-face meeting can be setup by including in the resource description the identification information of the resource (person), such as cell-phone number, email address, picture, physical description, etc. This information may be used together with the (possibly imprecise) location to help set up the face-to-face meeting. Thus, the individual's profile that is stored in MOBI-DIK will serve as a “wearable web-site”. Similarly, MOBI-DIK can facilitate face-to-face meetings in singles matchmaking.
Emergency Response, Homeland Security. MOBI-DIK offers the capability to extend decision-making and coordination capability. This finds applications in emergency environments, an area of particular concern to the government trying to find technologies that can be exploited to support the more than eight million first responders1 in U.S. homeland security. Consider workers in disaster areas, soldiers and military personnel operating in environments where the wireless fixed infrastructure is significantly degraded or non-existent. They would welcome a capability that lets them automatically propagate messages, pictures, or resource information to other workers, based on matching profiles, security, and attribute values rather than node-id. As mobile users involved in an emergency response naturally cluster around the location of interest, a self-forming, high-bandwidth network that allows secure point-to-point or point-to-multipoint communication without the need of potentially compromised infrastructure could be of great benefit. For instance, a picture of a wanted person could be propagated to all those involved in a targeted search at the scene. 1First responders are the personnel of organizations and agencies such as emergency medical services; fire, rescue, and hazardous material response teams; security and law enforcement agencies; relief organizations.
Consider a related emergency response application. Scientists are developing cockroach-sized robots or sensors that are carried by real cockroaches, which are able to search victims in exploded or earthquake-damaged buildings. These robots or sensors are equipped with radio transmitters. When a robot discovers a victim by sensing carbon dioxide, it may not have the transmission power to reach the outside rescuers; it can use local data dissemination to propagate the information to human rescuers outside the rubble. Sensors can also be installed on wild animals for endangered species assistance. A sensor monitors its carrier's health condition, and it disseminates an alert when an emergency symptom is detected.
Another potential application of MOBI-DIK is shipping container monitoring and inspection, in which sensors mounted on neighbouring containers can communicate and transitively relay alerts to remote checkpoints.
Mobile E-commerce. Consider short-range wireless broadcast and MANET dissemination of a merchant's sale and inventory information. It will enable a customer (whose cell phone is MOBI-DIK enabled) that enters a mall to locate a desired product at the best price. When a significant percentage of people have mobile devices that can query retail data, merchants will be motivated to provide inventory/sale/coupons information electronically to nearby potential customers. The information can be provided and disseminated (in, say, a mall or airport) by the MOBI-DIK software.
Airport Applications. Airports provide several different opportunities for the use of MOBI-DIK. From the point of view of commerce, airports have stores and kiosks where merchandise is sold similarly to a mall. Imagine arriving at a large airport and realizing you do not have the computer power cord you need for your presentation. MOBI-DIK will enable a user to search for the needed product—just like in a mall. Merchants can similarly provide their location information and offer promotional incentives to passengers.
MOBI-DIK can also be used by airport personnel to coordinate their activities. This is especially important when there is a communication failure due an emergency that degrades the infrastructure. Like the case of early responders, airport personnel can continue to coordinate their activities through the use of the MANET network that is available even though the infrastructure is not functioning. Another potential opportunity that will benefit both the travelers and the airport operations is the dissemination of real-time information regarding flight changes, delays, queue length, parking information, special security alerts and procedures, and baggage information. This can augment the audio announcements that often cannot be heard in restaurants, stores, or restrooms, and the limited number of displays.
Transportation Safety and Efficiency. MOBI-DIK software can improve safety and mobility by enabling travelers to cooperate intelligently and automatically. A vehicle will be able to automatically and transitively communicate to trailing vehicles its “slow speed” message when it encounters an accident, congestion, or dangerous road surface conditions. This will allow other drivers to make decisions such as finding alternative roads. Also, early warning messages may allow a following vehicle to anticipate sudden braking, or a malfunctioning brake light, and thus prevent pile-ups in some situations. Similarly, other resource information, such as ridesharing opportunities, transfer protection (transfer bus requested to wait for passengers), will be propagated transitively, improving efficiency of the transportation system.
Inefficiencies in the transportation system result in excessive environmental pollution, fuel consumption, risk to public safety, and congestion. Statistical data reveals that excess congestion cost the US economy over $69 billion in 2001 from fuel and wages alone. The amount of automobile travel has increased over the past two decades by 91%. The average annual delay due to traffic congestion has climbed over 300% in the past two decades, going from 7 hours spent stuck in traffic per person per year in 1982 to 26 hours in 2001.
Ridesharing (i.e., vehicles carrying more than one person, either publicly provided such as transit, a taxi, or a vanpool, or prearranged rides in a privately owned vehicle) and car sharing (i.e., a program that allows registered users to borrow a car on an hourly basis from fixed locations) have the potential to alleviate these problems. For example, the Illinois Dept. of Transportation is also sponsoring a ridesharing program in the AI lab at UIC.
Currently the matchmaking required in ridesharing is performed offline. However, the success of ridesharing will depend largely on the efficient identification and matching of riders/drivers to vehicles in real time in a local environment, which is where the benefit of our technology lies, providing information that is simultaneously relevant in time, location, and interest. MOBI-DIK incorporated in navigational devices and PDA's can be used to disseminate to other devices and PDA's information about relevant resources such as ridesharing partners, free parking slots, and available taxicabs or taxicab customers.